package com.sise.Array;

/**
 *      剑指 Offer 11. 旋转数组的最小数字
 *
 *      把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。
 *      例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。  
 *      输入：[3,4,5,1,2]
 *      输出：1
 *      输入：[2,2,2,0,1]
 *      输出：0
 *
 *      题解：直接看官方视频
 *
 *      这里采用的是二分查找法，以 中心点 和 最右点 进行比较，
 *      1、比如 [3,4,5,1,2] 中的 5 > 2，那么说明此时最小值在中心点的右边，故此 left = mid + 1。
 *      2、如果是 [4,5,1,2,3] 中 1 < 3，那么说明最小值在 mid 的右边 (包括 mid)，因为此时没办法判断 mid 是不是我们想要找的最小值。
 *      3、例如数组元素重复，[4,3,4,4,4] 中重复数字，那么在判断 mid 和 right 时，就会出现相等的时候，此时我们将 right - 1，
 *         由于 mid = (left + right) / 2, 所以 mid 也会减一，通过压缩重复数值，得到新的 mid，可能比 right 大或小，
 *         此时进入新一轮的判断， mid 更 大则结果在右边，mid 更小则结果在左边。
 *
 */
public class _offer_11_minArray {
    public int minArray(int[] numbers) {
        int left = 0;
        int right = numbers.length - 1;

        while (left < right){
            int mid = left + (right - left) / 2;    // int mid = left + ((right - left) >> 1); 这里要加括号，因为 + 优先级大于 >>
            if (numbers[mid] > numbers[right]){
                left = mid + 1;
            }else if (numbers[mid] < numbers[right]){
                right = mid;
            }else {
                right--;
            }
        }
        return numbers[left];
    }
}
